package datastructure.book.dp._1_pathway.all;

public class _5_Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] cntArr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    cntArr[i][j] = matrix[i][j];
                }else if (j == 0 && j + 1 < n) {
                    cntArr[i][j] = Math.min(cntArr[i-1][j],cntArr[i-1][j+1])+matrix[i][j];
                }else if (j > 0 && j + 1 < n) {
                    cntArr[i][j] = min(cntArr[i-1][j],cntArr[i-1][j-1],cntArr[i-1][j+1])+matrix[i][j];
                }else if (j == n - 1) {
                    cntArr[i][j] = Math.min(cntArr[i-1][j],cntArr[i-1][j-1])+matrix[i][j];
                }
            }
        }
        int result = cntArr[m-1][0];
        for (int i = 1; i < cntArr[m - 1].length; i++) {
            result = Math.min(cntArr[m-1][i],result);
        }
        return result;
    }

    private int min(int i,int j,int k){
        return Math.min(Math.min(i,j),k);
    }
}
